package com.example.tree24.tree;

/**
 * @description 二叉查找树
 * @auther lijiewei
 * @date 2021/9/14 16:32
 */
public class BinarySearchTree {

    /** 始终指向树根节点. */
    private Node tree;

    /**
     * 新增
     * @param data 数据
     * @return
     * @author lijiewei
     * @date   2021/9/15 9:43
     */
    public void add(int data) {
        if (tree == null) {
            tree = new Node(data);
            return;
        }
        Node p = tree;
        while (p != null) {
            if (data > p.getData()) {
                if (p.getRight() == null) {
                    p.setRight(new Node(data));
                    return;
                }
                p = p.getRight();
            } else {
                if (p.getLeft() == null) {
                    p.setLeft(new Node(data));
                    return;
                }
                p = p.getLeft();
            }
        }
    }

    /**
     * 查询
     * @param data 数据
     * @return
     * @author lijiewei
     * @date   2021/9/15 10:10
     */
    public Node get(int data) {
        Node p = tree;
        while (p != null) {
            if (data < p.getData()) {
                p = p.getLeft();
            } else if (data > p.getData()) {
                p = p.getRight();
            } else {
                return p;
            }
        }
        return null;
    }

    /**
     * 删除
     * @param data 数据
     * @return
     * @author lijiewei
     * @date   2021/9/15 10:18
     */
    public void delete(int data) {
        //指向要删除的节点，初始化指向根节点
        Node p = tree;
        //指向 p 的父节点
        Node pp = null;

        while (p != null && p.getData() != data) {
            pp = p;
            if (data > p.getData()) {
                p = p.getRight();
            } else {
                p = p.getLeft();
            }
        }
        if (p == null) {
            return;
        }

        //要删除的节点有两个子节点
        if (p.getLeft() != null && p.getRight() != null) {
            //右子树中最小节点
            Node minP = p.getRight();
            //minP 的父节点
            Node minPP = p;
            while (minP.getLeft() != null) {
                minPP = minP;
                minP = minPP.getLeft();
            }
            //交换节点值
            p.setData(minP.getData());
            //要删除的节点变成了 minP，变成了删除叶子节点或者仅有一个子节点
            p = minP;
            pp = minPP;
        }

        //删除节点是叶子节点或者仅有一个子节点
        Node child = null; // p的子节点
        if (p.getLeft() != null) {
            child = p.getLeft();
        } else if (p.getRight() != null) {
            child = p.getRight();
        }

        //删除节点
        if (pp == null) { // 删除根节点
            tree = child;
        } else if (pp.getLeft() == p) {
            pp.setLeft(child);
        } else {
            pp.setRight(child);
        }
    }

    /**
     * 查找最小
     * @author lijiewei
     * @date   2021/9/15 10:59
     */
    public Node findMin() {
        if (tree == null) {
            return null;
        }
        Node p = tree;
        while (p.getLeft() != null) {
            p = p.getLeft();
        }
        return p;
    }

    /**
     * 查找最大
     * @return
     * @author lijiewei
     * @date   2021/9/15 14:24
     */
    public Node findMax() {
        if (tree == null) {
            return null;
        }
        Node p = tree;
        while (p.getRight() != null) {
            p = p.getRight();
        }
        return p;
    }
}
